package cuppics;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;

import org.junit.Test;

public class Prj23 {

	/**
	 * A perfect number is a number for which the sum of its proper divisors is
	 * exactly equal to the number. For example, the sum of the proper divisors
	 * of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect
	 * number.
	 * 
	 * A number n is called deficient if the sum of its proper divisors is less
	 * than n and it is called abundant if this sum exceeds n.
	 * 
	 * As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the
	 * smallest number that can be written as the sum of two abundant numbers is
	 * 24. By mathematical analysis, it can be shown that all integers greater
	 * than 28123 can be written as the sum of two abundant numbers. However,
	 * this upper limit cannot be reduced any further by analysis even though it
	 * is known that the greatest number that cannot be expressed as the sum of
	 * two abundant numbers is less than this limit.
	 * 
	 * Find the sum of all the positive integers which cannot be written as the
	 * sum of two abundant numbers.
	 */
	@Test
	public void test() {
		System.out.println(Calculator.calculate(28123));
	}

	public static class Calculator {

		public static int calculate(int upLimit) {

			List<Integer> abundantList = new ArrayList<Integer>();

			// 1, 2 , 3,
			for (int i = 1; i < upLimit; i++) {

				int sum = sumAllDivisors(getAllDivsors(i));
				if (sum - i > i) {
					abundantList.add(i);
				}
			}

			Set<Integer> set = new HashSet<Integer>();
			for (int i = 0; i < abundantList.size(); i++) {
				for (int j = 0; j < abundantList.size(); j++) {
					set.add(abundantList.get(i) + abundantList.get(j));
				}
			}

			BitSet bt = new BitSet(upLimit);

			for (int i = 1; i <= upLimit; i++) {
				if (set.contains(i)) {
					bt.set(i - 1);
				}
			}

			int sum = 0;
			for (int i = 0; i < upLimit; i++) {
				if (!bt.get(i)) {
					sum += (i + 1);
				}
			}

			return sum;
		}

		/**
		 * more simple method use Sigma(p^n) = [p^(n+1)]-1/(p-1)
		 * 
		 * @param divisors
		 * @return
		 */
		public static int sumAllDivisors(List<Integer> divisors) {
			int sum = 0;
			for (Integer i : divisors) {
				sum += i;
			}
			return sum;
		}

		public static List<Integer> getAllDivsors(int num) {

			List<Integer> primeList = new ArrayList<Integer>();

			IntegerDivisor div = new IntegerDivisor();
			div.divisor(num);

			try {
				Calculator.iterList(primeList, div.primeMap);
			} catch (Exception e) {
				e.printStackTrace();
			}

			int sum = 1;
			for (Entry<Long, Integer> entry : div.primeMap.entrySet()) {
				sum *= (entry.getValue() + 1);
			}

			assert (primeList.size() == sum);
			return primeList;
		}

		/**
		 * 迭代获取所有因子
		 * 
		 * @param divisorList
		 * @param primeMap
		 * @throws Exception
		 */
		public static void iterList(List<Integer> divisorList,
				Map<Long, Integer> primeMap) throws Exception {

			// empty
			if (primeMap.keySet().size() == 0) {
				return;
			}

			// one
			if (primeMap.keySet().size() == 1) {

				for (Entry<Long, Integer> entry : primeMap.entrySet()) {
					Long prime = entry.getKey();

					for (int i = 0; i <= entry.getValue(); i++) {
						divisorList.add((int) Math.pow(prime, i));
					}
				}

				return;
			}

			if (primeMap.keySet().size() <= 1)
				throw new Exception("iter error !!!");

			assert (primeMap.keySet().size() > 1);

			for (Entry<Long, Integer> entry : primeMap.entrySet()) {
				Long prime = entry.getKey();
				int times = entry.getValue();

				List<Integer> tmp = new ArrayList<Integer>();

				Map<Long, Integer> primeMapCopy = copyMapExceptKey(primeMap,
						prime);

				for (int i = 0; i <= times; i++) {

					List<Integer> iterRemoveThisPrime = new ArrayList<Integer>();

					iterList(iterRemoveThisPrime, primeMapCopy);

					for (int iter = 0; iter < iterRemoveThisPrime.size(); iter++) {
						tmp.add((int) (Math.pow(prime, i) * iterRemoveThisPrime
								.get(iter)));
					}

				}

				copyArrs(tmp, divisorList);

			}

			return;

		}

		private static Map<Long, Integer> copyMapExceptKey(
				Map<Long, Integer> primeMap, Long prime) {

			HashMap<Long, Integer> ret = new HashMap<Long, Integer>(primeMap);
			ret.remove(prime);

			return ret;
		}

		private static void copyArrs(List<Integer> tmp,
				List<Integer> divisorList) {

			divisorList.clear();
			divisorList.addAll(tmp);

		}

	}

	/**
	 * 因子分解
	 * 
	 * @author 1440
	 * 
	 */
	public static class IntegerDivisor {

		public Map<Long, Integer> primeMap = new HashMap<Long, Integer>();
		public List<Long> primeList = new ArrayList<Long>();

		public void clear() {
			primeMap.clear();
			primeList.clear();
		}

		public void divisor(long num) {

			if (num <= 1)
				return;

			long prime = getPrime(
					num,
					primeList.size() == 0 ? 2
							: primeList.get(primeList.size() - 1));
			if (prime < 0) {
				primeMap.put(num, 1);
				primeList.add(num);
				return;
			} else {

				primeList.add(prime);
				int count = 0;
				do {

					count += 1;
					num = num / prime;
				} while (num % prime == 0);

				primeMap.put(prime, count);

				divisor(num);

			}

		}

		private long getPrime(long num, long start) {

			for (long i = start; i <= Math.sqrt(num); i++) {
				if (num % i == 0) {
					return i;
				}
			}
			return -1;
		}

		@Override
		public String toString() {

			return print_Map(this.primeMap);
		}

		public Long getLargestPrime() {
			return primeList.get(primeList.size() - 1);
		}

	}

	public static String print_Map(Map<?, ?> primeMap) {
		StringBuilder sb = new StringBuilder();
		for (Entry<?, ?> entry : primeMap.entrySet()) {
			sb.append(entry.getKey().toString() + "="
					+ entry.getValue().toString() + "\n");
		}
		return sb.toString();
	}

	public static void print_List(List<Integer> list) {
		for (int i = 0; i < list.size(); i++) {
			System.out.print(list.get(i) + ",");
		}
		System.out.println();
	}
}
